package com.company.algo.SearchAlgorithm.BT;
//最大路径和(4个方向可以走，所以无法用DP)
public class MaxPathSum {
    public static void main(String[] args) {
        int[][] graph = new int[3][];
        graph[0] = new int[]{3, 6, 0};
        graph[1] = new int[]{5, 8, 7};
        graph[2] = new int[]{0, 9, 0};


        visited = new boolean[graph.length][graph[0].length];
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[0].length; j++) {
                if (graph[i][j] != 0) {    //起点
                    visited[i][j] = true;
                    dfs(i, j, graph,graph[i][j]);
                    visited[i][j] = false;
                }
            }
        }
        System.out.println(ret);
    }
    static int ret = 0;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static boolean[][] visited;

    private static void dfs(int x, int y, int[][] graph,int val) {
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if (nextX >= 0 && nextX < graph.length && nextY >= 0 && nextY < graph[0].length
                    && !visited[nextX][nextY] && graph[nextX][nextY] > 0) {
                visited[nextX][nextY] = true;
                val += graph[nextX][nextY];
                ret = Math.max(val,ret);
                dfs(nextX, nextY, graph,val);
                val -= graph[nextX][nextY];
                visited[nextX][nextY] = false;
            }
        }

    }
}
